/*
https://leetcode.cn/problems/longest-palindromic-substring/
5. 最长回文子串
*/
class Solution { 
public:
    string longestPalindrome(string s) { 
        int n = s.size(); // 获取字符串长度
        vector<vector<bool>> dp(n, vector<bool>(n)); //二维布尔数组dp存取每次递推值供后续递推使用。
                                                     //其中dp[i][j]: 表示s[i...j]是否回文
        int start = 0; // 记录最长回文子串的起始位置
        int maxLen = 1; // 记录最长回文子串的长度，初始值为1（单字符回文）
        // 初始化长度为1和长度为2的情况，为后面长度>=3的情况的递推做准备
        for (int i = 0; i < n; i++) {
            dp[i][i] = true; 
        }
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }
        //长度>=3的递推
        for (int len = 3; len <= n; len++) { // len: 当前子串长度
            for (int i = 0; i < n - len + 1; i++) { // i: 子串的起始位置
                int j = i + len - 1; // j: 子串的结束位置
                // 检查子串的首尾字符是否相等，且中间的子串是否为回文
                if (s[i] == s[j] && dp[i + 1][j - 1]) { 
                    dp[i][j] = true;
                    start = i; // 更新最长回文子串的起始位置
                    maxLen = len; // 更新最长回文子串的长度
                }
            }
        }
        return s.substr(start, maxLen); // substr: 返回从start开始，长度为maxLen的子串
    }
};